package com.greedy;

import java.util.Arrays;

public class Solution09 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            } else if (k == 0 || nums[i]>=0) break;
        }
        if (k!=0) {
            k = k%2;
            Arrays.sort(nums);
            if (k==1) nums[0] = - nums[0];
        }
        for (int i = 0; i < nums.length; i++) {
            res += nums[i];
        }
        return res;
    }
}
